package top;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * 课程表
 *
 * @author chenyw
 * @date 2022/7/16 21:10
 */
public class Top207canFinish {
    //方法一：拓扑排序，以此消除入度为0的节点
    //prerequisites中的数字都在0，numCourses中
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] input = new int[numCourses];
        //统计入读为0的节点
        for (int[] pre : prerequisites) {
            input[pre[0]]++;
        }
        //将入度为零的节点添加到队列
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (input[i] == 0) {
                queue.addLast(i);
            }
        }
        int count = 0;
        //依次消除入度为0的节点
        while (!queue.isEmpty()) {
            Integer node = queue.pollFirst();
            count++;
            //将入度为0的节点加入队列
            for (int[] pre : prerequisites) {
                if (node == pre[1]) {
                    input[pre[0]]--;
                    if (input[pre[0]] == 0) {
                        queue.addLast(pre[0]);
                    }
                }
            }
        }
        return count == numCourses;
    }
}

